public class Algorithm {
    
    // 稳定性：列表中有两个相同的数 A=B，排序前A在B前面，排序后A依旧在B前面，则称为稳定，反之则称为不稳定
    // 稳定性的意义：使数据初始顺序不至于毫无意义
    
    /**
     * 选择排序
     * 每次从无序列表中找出最小的元素，跟第一个元素交换
     * 最优时间复杂度：O(n^2)，最差复杂度：O(n^2)，平均时间复杂度：O(n^2)，空间复杂度：O(1)，稳定性：不稳定
     *
     * @param array 待排序列表
     * @return 数据从小到大的列表
     */
    static void selectSort(int[] array) {
        // 遍历有序区
        for (int i = 0; i < array.length; i++) {
            
            // 找出无序区最小元素位置
            int index = i;
            for (int j = i; j < array.length; j++) {
                if (array[j] < array[index]) {
                    index = j;
                }
            }
            
            // 交换元素位置
            int temp = array[i];
            array[i] = array[index];
            array[index] = temp;
        }
    }
    
    /**
     * 冒泡排序
     * 对比相邻元素大小，不符合排序的交换位置
     * 最优时间复杂度：O(n)，最差复杂度：O(n^2)，平均时间复杂度：O(n^2)，空间复杂度：O(1)，稳定性：稳定
     *
     * @param array 待排序列表
     * @return 数据从小到大的列表
     */
    static void bubblingSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            for (int j = i + 1; j < array.length; j++) {
                if (array[i] > array[j]) {
                    int temp = array[i];
                    array[i] = array[j];
                    array[j] = temp;
                }
            }
        }
    }
    
    /**
     * 插入排序
     * 根据元素大小，插入到前面有序列表中
     * 最优时间复杂度：O(n)，最差复杂度：O(n^2)，平均时间复杂度：O(n^2),空间复杂度：O(1)，稳定性：稳定
     *
     * @param array 待排序列表
     * @return 数据从小到大的列表
     */
    static void insertSort(int[] array) {
        int i, j, k;
        // 遍历无序区
        for (i = 1; i < array.length; i++) {
            // 遍历有序区
            for (j = i - 1; j >= 0; j--) {
                if (array[j] < array[i]) {
                    break;
                }
            }
            
            if (j != i - 1) {
                // 插入元素
                int temp = array[i];
                for (k = i - 1; k > j; k--) {
                    array[k + 1] = array[k];
                }
                array[k + 1] = temp;
            }
        }
    }
    
    /**
     * 希尔排序
     * 其实就是分组插入排序，也称为缩小增量排序，比普通插入排序拥更好的性能
     * 最优时间复杂度：O(n)，最差复杂度：O(n^2)，平均时间复杂度：O(n^1.3),空间复杂度：O(1)，稳定性：不稳定
     *
     * @param array 待排序列表
     * @return 数据从小到大的列表
     */
    static void shellSort(int[] array) {
        // dk 增量
        for (int dk = array.length >> 1; dk > 0; dk = dk >> 1) {
            // 遍历分组
            for (int i = 0; i < dk; i++) {
                // 遍历组内元素
                for (int j = i + dk; j < array.length; j += dk) {
                    // 比较相邻元素大小
                    if (array[j - dk] > array[j]) {
                        int temp = array[j];
                        int k = j - dk;
                        // 插入元素，因为后期每组的数据都是相对有序的，可以得出相邻的数据更为接近，所以这里遍历是从 k = j -dk 开始
                        while (k >= 0 && array[k] > temp) {
                            array[k + dk] = array[k];
                            k -= dk;
                        }
                        array[k + dk] = temp;
                    }
                }
            }
        }
    }
    
    /**
     * 归并排序
     * 归并排序就是使用把列表递归成短列表，递归的出口是短列表只有一个元素的时候
     * 然和把个个短列表合并成一个有序的长列表，不断合并知道列表全部有序
     * 最优时间复杂度：O(log n)，最差复杂度：O(log n)，平均时间复杂度：O(log n)，稳定性：稳定
     *
     * @param array 待排序列表
     * @return 数据从小到大的列表
     */
    static void mergeSort(int[] array) {
        mergeSortRecursion(array, 0, array.length - 1);
    }
    
    private static void mergeSortRecursion(int[] array, int left, int right) {
        if (left < right) {
            int middle = (left + right) / 2;
            mergeSortRecursion(array, left, middle); // 递归左边
            mergeSortRecursion(array, middle + 1, right); // 递归右边
            merge(array, left, middle, right); // 合并两个有序列表
        }
    }
    
    private static void merge(int[] array, int left, int middle, int right) {
        int leftIndex = left;
        int rightIndex = middle + 1;
        int[] tempArr = new int[right - leftIndex + 1];
        int i = 0;
        // 判断大小插入数据，直到有一边先插完
        while (leftIndex <= middle && rightIndex <= right) {
            if (array[leftIndex] < array[rightIndex]) {
                tempArr[i++] = array[leftIndex++];
            } else {
                tempArr[i++] = array[rightIndex++];
            }
        }
        // 判断左边列表是否插入完
        while (leftIndex <= middle) tempArr[i++] = array[leftIndex++];
        // 判断右边列表是否插入完
        while (rightIndex <= right) tempArr[i++] = array[rightIndex++];
        // 把有序列表插入原列表
        for (i = 0; i < tempArr.length; i++) {
            array[left++] = tempArr[i];
        }
    }


//    static int[] bubblingSort(int[] array){
//        return array;
//    }


}
